package com.algorithm.排序.基于比较的排序;

import com.algorithm.排序.Sort;

//堆排序可以认为是对选择排序的一种优化
public class 堆排序<E extends Comparable<E>> extends Sort<E> {
    private int heapSize;

    @Override
    protected void sort() {
        //原地建堆
        // 自下而上的下滤
        heapSize = array.length;
        for (int i = ( heapSize>> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1){
            //交换堆顶元素和尾部元素
            swap(0,--heapSize);

            //对0位置进行siftDown
            siftDown(0);
        }
    }

    /**
     * 让索引位置的元素下滤
     * @param index
     */
    private void siftDown(int index) {
        E element = array[index];
        //非叶子节点数量
        int half = heapSize >> 1;

        //第一个叶子节点的索引 == 非叶子节点的数量
        //必须保证index位置是叶子节点
        while (index < half) {
            //index的节点有两种情况
            //1. 只有左子节点
            //2. 同时有左右节点

            //找出左右节点较大的那一个
            //默认先拿左子节点的索引
            int childIndex = (index << 1) + 1;
            E child = array[childIndex];

            //右子节点
            int rightIndex = childIndex + 1;

            //选出左右节点最大的那个
            if (rightIndex < heapSize && cmp(array[rightIndex],child) > 0){
                child = array[childIndex =rightIndex];
            }

            if (cmp(element,child) >= 0) break;

            //将子节点放到存放index位置
            array[index] = child;
            //重新设置index
            index = childIndex;
        }
        array[index] = element;
    }

}
